package priorityQueue;

// 优先级队列(堆)的模拟实现

import java.util.Arrays;

public class PriorityQueue {
    public int[] elem;
    public int usedSize;

    // 构造方法：进行变量初始化
    public PriorityQueue() {
        this.elem = new int[10];
        this.usedSize = 0; // 有效长度
    }

    // 初始化数组
    public void initArray(int[]arr) {
        this.elem = Arrays.copyOf(arr,arr.length); //将数组中元素拷贝给数组
        this.usedSize = this.elem.length;
    }

    /**
     * 建堆的时间复杂度：差比数列求和--O(N)
     * 注意：从最后一个根节点依次向上的根结点遍历，以使得每棵子树都是大堆形式--使用根结点循环
     * @param array
     */
    public void createHeap(int[] array) {
        // 注意：如果这里不传参时，usedSize就不用重新计算，直接使用initArray中已经初始化好的就行；
        // 其实，就算传入数组参数也可以直接使用this.usedSize
        int usedSize = array.length;
        for (int parent=(usedSize-1)/2; parent>=0; parent--) {
            shiftDown(parent,usedSize);  // 注意结束条件是数组长度！
        }
    }

    /**
     * 向下调整(一次针对的是一棵子树）--大根堆
     * 比较左右孩子结点大小，找到最大，然后与根结点进行比较，若果根结点小就进行交换--循环实现
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root,int len) {
        int child = 2*root+1; // 左孩子结点
        while(child < len) { // 进入循环的条件其实是：好孩子结点要小于数组长度
            // 判断左右孩子结点大小：
            if((child+1<len) && (elem[child]<elem[child+1])) {
                child++; // 赤裸裸的记录最大孩子结点的下标
            }
            // 来到这儿说明两种情况：只有左孩子or左孩子小于右孩子--两种情况都是child结点有最大值
            // 判断最大子结点和父亲节点的大小 -- 进行交换swap
            if(elem[child] > elem[root]) {
                swap(elem,child,root);
                // child root变化
                root = child;
                child = 2*root+1;
            } else {
                // 说明是：父亲节点大
                break;
            }
        }
    }

    private void swap(int[] elem, int child, int root) {
        int tmp = elem[child];
        elem[child] = elem[root];
        elem[root] = tmp;
    }


    /**
     * 入队是先加在尾部 然后进行向上调整
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()) {
            // 进行扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        // 要么扩容成功，要么未满 就开始进行尾插
        this.elem[this.usedSize] = val;
        this.usedSize++; // 要注意++！！
        // 向上调整：
        shiftUp(this.usedSize-1); // 因为之前已经usedSize++l，此时有效下标需要--
    }

    // 向上调整：也是孩子结点与父亲节点比较
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        // 注意调整条件：child>0
        while(child>0) {
            // 直接与父亲节点进行比较就行，不需要再与另一个孩子结点进行比较，因为其他已经是有序的大根堆
            if(this.elem[parent] < this.elem[child]) {
                swap(this.elem,child,parent);
                // 注意交换后一定要进行变量的变化
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return this.usedSize==this.elem.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素!! 即：删除的是堆顶元素！
     * 仍然要保持是大根堆
     * 把堆顶数据域最后一个数据进行交换，然后进行向下调整成大根堆
     */
    public void pollHeap() {
        if(isEmpty()) {
            return;
        }
        int old = this.elem[0];
        swap(this.elem,this.usedSize-1,0);
        this.usedSize--; // 此时有效数据中被换到最后的数据就不被包含在内

        // 注意该方法其实是在<usdSize时进行变换，所以不需要-1！！！
        //shiftDown(0,this.usedSize-1); // 向下调整
        shiftDown(0,this.usedSize);
        System.out.println(old);
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return this.elem[0];
    }
}
